home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / raytrace / radiance / simplerd.lha / simplerad / FinalFTP / Light / scull.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-21  |  23.2 KB  |  698 lines
  1. /**********************************************************************/
  2. /* scull.c                                                            */
  3. /*                                                                    */
  4. /* Shaft culling using [Haines and Wallace91] algorithm               */
  5. /*                                                                    */
  6. /* Copyright (C) 1992, Bernard Kwok                                   */
  7. /* All rights reserved.                                               */
  8. /* Revision 1.0                                                       */
  9. /* May, 1992                                                          */
  10. /**********************************************************************/
  11. #include <stdio.h>
  12. #include <math.h>
  13. #include "geo.h"
  14. #include "struct.h"
  15. #include "misc.h"
  16. #include "io.h"
  17. #include "bvol.h"
  18. #include "scull.h"
  19.  
  20. extern double Poly_PlaneD();
  21. extern OptionType Option;
  22. extern BoundingBoxType BoxPoly();
  23. extern int Bounds_Compare();
  24. extern int objlist_size;
  25. extern void BoxInit();
  26. extern Vector Nearest_Point(), Farthest_Point();
  27. extern FILE *rlogfile;
  28.  
  29. /**********************************************************************/
  30. BoundingBoxType extentbox; /* Minimum extent box around bounding boxes */
  31. RefListtype scull, rcull;  /* Edges of culling shaft */
  32. PlaneSettype planeset;     /* Planes in culling shaft */
  33. ShaftStatstype ShaftStats; /* Shaft statistics */
  34.  
  35. /**********************************************************************/
  36. /* Initialize shaft stats for current shaft                           */
  37. /**********************************************************************/
  38. void StartShaft()
  39. {
  40.   ShaftStats.BoxIn = ShaftStats.BoxOut = ShaftStats.BoxOverlap = 
  41.     ShaftStats.BoxContains = ShaftStats.BoxTests = 0;
  42.   ShaftStats.candCube = ShaftStats.candSphere = ShaftStats.candCone = 
  43.     ShaftStats.candMesh = ShaftStats.candCyl = ShaftStats.candHbox = 0;
  44.   ShaftStats.candidates = 0; 
  45. }
  46.  
  47. /**********************************************************************/
  48. /* Initialize stats for all shafts                                    */
  49. /**********************************************************************/
  50. void Init_ShaftStats()
  51. {
  52.   ShaftStats.total_BoxIn = ShaftStats.total_BoxOut = 
  53.     ShaftStats.total_BoxOverlap = 
  54.     ShaftStats.BoxContains = ShaftStats.BoxTests = 0;
  55.   ShaftStats.total_shafts = 0; 
  56.   ShaftStats.total_candidates = 0; 
  57. }
  58.  
  59. /**********************************************************************/
  60. /* Update stats for shaft(s)                                          */
  61. /**********************************************************************/
  62. void Update_ShaftStats(candidate, primid)
  63.      int candidate;
  64.      int primid;
  65. {
  66.   switch (candidate) {
  67.   case INSIDE: ShaftStats.BoxIn++; break;
  68.   case OVERLAP: ShaftStats.BoxOverlap++; break;
  69.   case CONTAINS: ShaftStats.BoxContains++; break;
  70.   case OUTSIDE: ShaftStats.BoxOut++; break;
  71.   default: break;
  72.   }
  73.  
  74.   if (candidate != OUTSIDE) { 
  75.     switch (primid) {
  76.     case CONE: ShaftStats.candCone++; break;
  77.     case CUBE: ShaftStats.candCube++; break;
  78.     case SPHERE: ShaftStats.candSphere++; break;
  79.     case CYLINDER: ShaftStats.candCyl++; break;
  80.     case MESH: ShaftStats.candMesh++; break;
  81.     case HBOX: ShaftStats.candHbox++; break;
  82.     default: 
  83.       fprintf(stderr, "Invalid candidate list primitive.\n");
  84.       exit(1);
  85.     }
  86.     ShaftStats.candidates++;
  87.   }
  88. }
  89.  
  90. /**********************************************************************/
  91. /* Print plane info                                                   */
  92. /**********************************************************************/
  93. void Print_Plane(pl)
  94.      Plane pl;
  95. {
  96.   printf("N=%g,%g,%g d=%g, pt=%g,%g,%g\n",
  97.      pl.n.x, pl.n.y, pl.n.z, pl.d, pl.p.x, pl.p.y, pl.p.z);
  98. }
  99.  
  100. /**********************************************************************/
  101. /* Print shaft information                                            */
  102. /**********************************************************************/
  103. void Print_Shaft(src,rec, fptr)
  104.      Polygon *src, *rec;
  105.      FILE *fptr;
  106. {
  107.   int i;
  108.  
  109.   fprintf(fptr,"\n\t** Shaft Information **\n");
  110.   fprintf(fptr,"\t|Candidate|= %d for patch%d and patch%d built\n",
  111.      objlist_size, src->id, rec->id);
  112.  
  113.   fprintf(fptr,"\tSource reference list ( ");
  114.   for(i=0;i<6;i++) fprintf(fptr,"%d ", scull.dir[i]);
  115.   fprintf(fptr,")\n");
  116.  
  117.   fprintf(fptr,"\tReceiver reference list ( ");
  118.   for(i=0;i<6;i++) fprintf(fptr,"%d ", rcull.dir[i]);
  119.   fprintf(fptr,")\n");
  120.  
  121.   fprintf(fptr,"\t|Plane Set|=%d {\n", planeset.num_planes);
  122.   for (i=0;i<planeset.num_planes;i++) {
  123.     fprintf(fptr,"\tPlane[%d]: ",i);
  124.     Print_Plane(planeset.planes[i]);
  125.   }
  126.   fprintf(fptr,"\t}\n");
  127.  
  128.   BoundsPrint(extentbox, stdout, "Extent Box");
  129. }
  130.  
  131. /**********************************************************************/
  132. /* Print stats for current iteration or final stats                   */
  133. /**********************************************************************/
  134. void EndShaft(final_stats, fptr)
  135.      int final_stats;
  136.      FILE *fptr;
  137. {
  138.   FILE *fp;
  139.   
  140.   if (Option.device == PRINT)       
  141.     fp = stdout;
  142.   else fp = fptr;
  143.  
  144.   if (!final_stats) {
  145.     ShaftStats.total_shafts++;
  146.     ShaftStats.total_candidates += ShaftStats.candidates;
  147.     ShaftStats.total_BoxTests += ShaftStats.BoxTests;
  148.     ShaftStats.total_BoxOverlap += ShaftStats.BoxOverlap;
  149.     ShaftStats.total_BoxContains += ShaftStats.BoxContains;
  150.     ShaftStats.total_BoxOut += ShaftStats.BoxOut;
  151.     ShaftStats.total_BoxIn += ShaftStats.BoxIn;
  152.   }
  153.  
  154.   if (Option.statistics) {
  155.     if (final_stats || Option.device == PRINT) {
  156.       fprintf(fp,"\n\tShaft Culling Statistics\n");
  157.       fprintf(fp,"\t--------------------------\n");
  158.       fprintf(fp,"\tStrategy used: ");
  159.       switch (ShaftStats.strategy) {
  160.       case RATIO_OPEN:
  161.     fprintf(fp,"\tRatio open = %g\n", ShaftStats.ratio_open); break;
  162.       case KEEP_CLOSED: fprintf(fp,"Keep closed\n"); break;
  163.       case ALWAYS_OPEN: fprintf(fp,"Always open\n"); break;
  164.       case OVERLAP_OPEN: fprintf(fp,"Overlap open\n"); break;
  165.       default: fprintf(fp,"Unknown ???\n");
  166.       } 
  167.  
  168.       if (Option.tablelog) {
  169.     switch (ShaftStats.strategy) {
  170.     case RATIO_OPEN:
  171.       fprintf(rlogfile,"RO %g \\\\\n", ShaftStats.ratio_open); break;
  172.     case KEEP_CLOSED: fprintf(rlogfile,"KC \\\\\n"); break;
  173.     case ALWAYS_OPEN: fprintf(rlogfile,"AO \\\\\n"); break;
  174.     case OVERLAP_OPEN: fprintf(rlogfile,"OO \\\\\n"); break;
  175.     default: fprintf(rlogfile,"Unknown ??? \\\\\n");
  176.     }
  177.       }
  178.     }
  179.     if (!final_stats) {
  180.       if (Option.device == PRINT) {
  181.     fprintf(fp,"\tNumber volumes tested: %d\n", ShaftStats.BoxTests);
  182.     fprintf(fp,"\t%In=%d; Out=%d; Overlap=%d; Contains=%d\n",
  183.         ShaftStats.BoxIn,
  184.         ShaftStats.BoxOut,
  185.         ShaftStats.BoxOverlap,
  186.         ShaftStats.BoxContains);
  187.       
  188.     fprintf(fp,"\tNumber of candidates %d\n", ShaftStats.candidates);
  189.     fprintf(fp,"\tCube=%d; Cone=%d; Cyl=%d; Sph=%d; Mesh=%d; HBV=%d\n",
  190.         ShaftStats.candCube,
  191.         ShaftStats.candCone,
  192.         ShaftStats.candCyl,
  193.           ShaftStats.candSphere,
  194.         ShaftStats.candMesh,
  195.         ShaftStats.candHbox);
  196.       }
  197.     } else {
  198.       fprintf(fp,"\tTotal boxes tested: %d\n", ShaftStats.total_BoxTests);
  199.       fprintf(fp,"\t%In=%d; Out=%d; Overlap=%d; Contains=%d\n",
  200.           ShaftStats.total_BoxIn,
  201.           ShaftStats.total_BoxOut,
  202.           ShaftStats.total_BoxOverlap,
  203.           ShaftStats.total_BoxContains);      
  204.       fprintf(fp,"\tTotal number of candidates: %d\n", 
  205.           ShaftStats.total_candidates);
  206.       fprintf(fp,"\tAverage candidates per shaft: %2.2f\n", 
  207.           (float) ShaftStats.total_candidates / 
  208.           (float) ShaftStats.total_shafts); 
  209.  
  210.       if (Option.tablelog) {
  211.     fp = rlogfile;
  212.     fprintf(fp,"%d \\\\\n", ShaftStats.total_BoxTests);
  213.     fprintf(fp,"%d \\\\\n%d \\\\\n%d \\\\\n%d \\\\\n",
  214.         ShaftStats.total_BoxIn,
  215.         ShaftStats.total_BoxOut,
  216.         ShaftStats.total_BoxOverlap,
  217.         ShaftStats.total_BoxContains);      
  218.     fprintf(fp,"%d \\\\\n", 
  219.         ShaftStats.total_candidates);
  220.     fprintf(fp,"%g \\\\\n", 
  221.         (float) ShaftStats.total_candidates / 
  222.         (float) ShaftStats.total_shafts); 
  223.       }
  224.     }
  225.     printf ("\n");
  226.   }
  227. }
  228.  
  229. /**********************************************************************/
  230. /* Form EXTENT BOX containing reference items, and find culling edges */
  231. /**********************************************************************/
  232. void Form_Extent_Culledges(extentbox, scull, rcull, sbox, rbox)
  233.      BoundingBoxType *extentbox, sbox, rbox;
  234.      RefListtype *scull, *rcull;
  235. {
  236.   int i;
  237.  
  238.   /* Initialize reference item lists, and extent box */
  239.   for (i=0;i<6;i++)
  240.     scull->dir[i] = rcull->dir[i] = FALSE;
  241.   BoxInit(extentbox);
  242.  
  243.   /* Check min x coordinates */
  244.   if (sbox.min.x < rbox.min.x) {
  245.     scull->pt[MINX] = extentbox->min.x = sbox.min.x;
  246.     scull->dir[MINX] = TRUE;
  247.   } else {
  248.     rcull->pt[MINX] = extentbox->min.x = rbox.min.x;
  249.     if (sbox.min.x != rbox.min.x)
  250.       rcull->dir[MINX] = TRUE;
  251.   }  
  252.  
  253.   /* Check min y coordinates */
  254.   if (sbox.min.y < rbox.min.y) {
  255.     scull->pt[MINY] = extentbox->min.y = sbox.min.y;
  256.     scull->dir[MINY] = TRUE;
  257.   } else { 
  258.     rcull->pt[MINY] = extentbox->min.y = rbox.min.y;
  259.     if (sbox.min.y != rbox.min.y) 
  260.       rcull->dir[MINY] = TRUE;
  261.   }  
  262.  
  263.   /* Check min z coordinates */
  264.   if (sbox.min.z < rbox.min.z) {
  265.     scull->pt[MINZ] = extentbox->min.z = sbox.min.z;
  266.     scull->dir[MINZ] = TRUE;
  267.   } else {
  268.     rcull->pt[MINZ] = extentbox->min.z = rbox.min.z;
  269.     if (sbox.min.z != rbox.min.z) 
  270.       rcull->dir[MINZ] = TRUE;
  271.   }  
  272.  
  273.   /* Check max x coordinates */
  274.   if (sbox.max.x > rbox.max.x) {
  275.     scull->pt[MAXX] = extentbox->max.x = sbox.max.x;
  276.     scull->dir[MAXX] = TRUE;
  277.   } else { 
  278.     rcull->pt[MAXX] = extentbox->max.x = rbox.max.x;
  279.     if (sbox.max.x != rbox.max.x) 
  280.       rcull->dir[MAXX] = TRUE;
  281.   }  
  282.  
  283.   /* Check max y coordinates */
  284.   if (sbox.max.y > rbox.max.y) {
  285.     scull->pt[MAXY] = extentbox->max.y = sbox.max.y;
  286.     scull->dir[MAXY] = TRUE;
  287.   } else { 
  288.     rcull->pt[MAXY] = extentbox->max.y = rbox.max.y;
  289.     if (sbox.max.y != rbox.max.y) 
  290.       rcull->dir[MAXY] = TRUE;
  291.   }  
  292.  
  293.   /* Check max z coordinates */
  294.   if (sbox.max.z > rbox.max.z) {
  295.     scull->pt[MAXZ] = extentbox->max.z = sbox.max.z;
  296.     scull->dir[MAXZ] = TRUE;
  297.   } else {
  298.     rcull->pt[MAXZ] = extentbox->max.z = rbox.max.z;
  299.     if (sbox.max.z != rbox.max.z) 
  300.       rcull->dir[MAXZ] = TRUE;
  301.   }  
  302. }
  303.  
  304. /**********************************************************************/
  305. /* Form plane set from reference lists:                               */
  306. /* Form all combinations of elements on one reference list with those */
  307. /* on the other, ignoring combinations with matching directions       */
  308. /* (X, Y or Z)                                                        */
  309. /**********************************************************************/
  310. void Form_Plane_Set(planeset, scull, rcull, sbox, rbox)
  311.      PlaneSettype *planeset;
  312.      RefListtype scull, rcull;
  313.      BoundingBoxType sbox, rbox;
  314. {
  315.   int i,j;
  316.   Vector plane_pt;              /* Vector used to compute plane distance */
  317.   Vector N;
  318.   double d, tmp;
  319.  
  320.   planeset->num_planes = 0;
  321.   for (i=0;i<6;i++)        /* Check all/any source cull edges */
  322.     for(j=0;j<6;j++)       /* Check all/any receiver cull edges */
  323.       if ((i != j) && scull.dir[i] && rcull.dir[j])  {        
  324.     if ( ((i < j) && ((i+3) != j)) || ((i > j) && ((j+3) != i)) ) {
  325.         
  326.       /* Form a new plane for plane set of culling shaft.
  327.          Note: sample point on plane taken from source box,
  328.          could just as well be taken from the receiver box */
  329.       planeset->planes[planeset->num_planes].n.x = 0.0;
  330.       planeset->planes[planeset->num_planes].n.y = 0.0;
  331.       planeset->planes[planeset->num_planes].n.z = 0.0;
  332.       plane_pt.x = plane_pt.y = plane_pt.z = 0.0;
  333.  
  334.       /* Check source edge list */
  335.       switch (i) {
  336.       case MINX: 
  337.         plane_pt.x = sbox.min.x;    tmp = rbox.min.x - sbox.min.x; 
  338.         break;
  339.       case MAXX: 
  340.         plane_pt.x = sbox.max.x;    tmp = rbox.max.x - sbox.max.x; 
  341.         break;
  342.       case MINY: 
  343.         plane_pt.y = sbox.min.y;    tmp = rbox.min.y - sbox.min.y; 
  344.         break;
  345.       case MAXY: 
  346.         plane_pt.y = sbox.max.y;    tmp = rbox.max.y - sbox.max.y;
  347.         break;
  348.       case MINZ: 
  349.         plane_pt.z = sbox.min.z;    tmp = rbox.min.z - sbox.min.z; 
  350.         break;
  351.       case MAXZ: 
  352.         plane_pt.z = sbox.max.z;    tmp = rbox.max.z - sbox.max.z; 
  353.         break;
  354.       default: 
  355.         fprintf(stderr,"Invalid axial direction of source edge\n");
  356.         exit(1);
  357.       }
  358.       if (j == MINX || j == MAXX)
  359.         planeset->planes[planeset->num_planes].n.x = tmp;
  360.       else if (j == MINY || j == MAXY)
  361.         planeset->planes[planeset->num_planes].n.y = tmp;
  362.       else if (j == MINZ || j == MAXZ)
  363.         planeset->planes[planeset->num_planes].n.z = tmp;
  364.  
  365.       /* Check receiver edge list */
  366.       switch (j) {
  367.       case MINX:
  368.         plane_pt.x = sbox.min.x;    tmp = sbox.min.x - rbox.min.x; 
  369.         break;
  370.       case MAXX:
  371.         plane_pt.x = sbox.max.x;    tmp = sbox.max.x - rbox.max.x; 
  372.         break;
  373.       case MINY:
  374.         plane_pt.y = sbox.min.y;    tmp = sbox.min.y - rbox.min.y; 
  375.         break;
  376.       case MAXY:
  377.         plane_pt.y = sbox.max.y;    tmp = sbox.max.y - rbox.max.y; 
  378.         break;
  379.       case MINZ:
  380.         plane_pt.z = sbox.min.z;    tmp = sbox.min.z - rbox.min.z; 
  381.         break;
  382.       case MAXZ:
  383.         plane_pt.z = sbox.max.z;    tmp = sbox.max.z - rbox.max.z; 
  384.         break;
  385.       default:
  386.         fprintf(stderr,"Invalid axial direction of receiver edge\n");
  387.         exit(1);
  388.       }
  389.       if (i == MINX || i== MAXX)
  390.         planeset->planes[planeset->num_planes].n.x = tmp;
  391.       else if (i == MINY || i== MAXY)
  392.         planeset->planes[planeset->num_planes].n.y = tmp;
  393.       else if (i == MINZ || i== MAXZ)
  394.         planeset->planes[planeset->num_planes].n.z = tmp;
  395.       
  396.       /* Find normal vector and d */
  397.       N = planeset->planes[planeset->num_planes].n;
  398.       norm(&N);
  399.       d = Poly_PlaneD(N, plane_pt);
  400.  
  401.       /* Check direction of normal */
  402.       if (!Bounds_Behind_Plane(&sbox, N, d) ||
  403.           !Bounds_Behind_Plane(&rbox, N, d)) {
  404.         N = *vnegate(&N);
  405.         d = -d;
  406.       }
  407.       /* Store N, d and pt on plane */
  408.       planeset->planes[planeset->num_planes].n = N;
  409.       planeset->planes[planeset->num_planes].d = d;
  410.       planeset->planes[planeset->num_planes].p = plane_pt;
  411.  
  412.       planeset->num_planes++;
  413.     }
  414.       }
  415. }
  416.  
  417. /**********************************************************************/
  418. /* Find culling shaft between bounding boxes of source and receiver   */
  419. /**********************************************************************/
  420. void Form_Culling_Shaft(sbox, rbox)
  421.      BoundingBoxType sbox, rbox;
  422. {
  423.   /* Form extent box and culling edges */
  424.   Form_Extent_Culledges(&extentbox, &scull, &rcull, sbox, rbox);
  425.  
  426.   /* Generate all planes which connect the edges of the 2 
  427.      reference boxes. */
  428.   Form_Plane_Set(&planeset, scull, rcull, sbox, rbox);
  429. }
  430.  
  431. /**********************************************************************/
  432. /* Find out if test box is a candidate                                */
  433. /**********************************************************************/
  434. int isCandidate(box, extbox, sbox, rbox, planeset)
  435.      BoundingBoxType *box, *extbox, *sbox, *rbox;
  436.      PlaneSettype planeset;
  437. {
  438.   int i;
  439.   int candidate = OUTSIDE;    /* Assume box is outside */
  440.   Vector near_corner, far_corner; /* Near and far corners of box */
  441.   Vector N;
  442.   double d;
  443.   char *tmp = "                                                  ";
  444.  
  445.   /* Test if test volume is inside, outside or overlapping extent box */
  446.   candidate = Bounds_Compare(box,extbox);
  447.   if ((candidate == CONTAINS) || (candidate == OUTSIDE))
  448.     return candidate;
  449.  
  450.   /* Test if test volume overlaps either reference item's bounding box */
  451.   candidate = Bounds_Compare(box,sbox);
  452.   if (candidate == OVERLAP || candidate == CONTAINS) return OVERLAP;
  453.   candidate = Bounds_Compare(box,rbox);
  454.   if (candidate == OVERLAP || candidate == CONTAINS) return OVERLAP;
  455.  
  456.   /* Test test volume against each plane of plane set */
  457.   i = 0;
  458.   candidate = INSIDE;
  459.   while ((candidate != OUTSIDE || candidate != OVERLAP) 
  460.      && i < planeset.num_planes)
  461.   {
  462.     N = planeset.planes[i].n;
  463.     d = planeset.planes[i].d;
  464.     near_corner = Nearest_Point(box, N, d);
  465.     far_corner = Farthest_Point(box, N, d);
  466.     if (dot(&N, &near_corner) + d >= 0.0) { /* Outside shaft */
  467.       candidate = OUTSIDE;
  468.     } else if (dot(&N, &far_corner) + d > 0.0) { /* Overlaps shaft */
  469.       candidate = OVERLAP;
  470.     }
  471.     i++;
  472.   }
  473.   return candidate;
  474. }
  475.        
  476. int fdbg = 0;
  477. /**********************************************************************/
  478. /* Form candidate list for current shaft. Traverse BV tree recursively*/
  479. /* If not testing children of BV at current level, if none of it's    */
  480. /* children is added then add the BV. Return number of BV's added at  */
  481. /* current level to check.                                            */
  482. /**********************************************************************/
  483. int Form_Candidate_List(shootPatch, recPatch, sbox, rbox, hbox)
  484.      Polygon *shootPatch, *recPatch;
  485.      BoundingBoxType *sbox, *rbox;
  486.      HBBox *hbox;
  487. {
  488.   int i;
  489.   int candidate;
  490.   float percent_overlap;
  491.   int overlap_id;
  492.   BoundingBoxType *test_box;
  493.   int atlevel_added;
  494.   int children_added;
  495.   int same_father;
  496.  
  497.   atlevel_added = 0;
  498.   if (hbox == NULL) return 0;
  499.   test_box = hbox->box;
  500.   
  501.   /* Test if test box is in front of source and receiver first */
  502.   candidate = ((1 - Bounds_Behind_Plane(test_box, shootPatch->normal[0],
  503.                     shootPatch->d)) &&
  504.            (1 - Bounds_Behind_Plane(test_box, recPatch->normal[0],
  505.                     recPatch->d)) );
  506.   if (!candidate) return 0;
  507.  
  508.   /* Test if box is inside the extent box, source or receiver box,
  509.      and finally the shaft */
  510.   candidate = isCandidate(test_box, &extentbox, sbox, rbox, planeset);
  511.   ShaftStats.BoxTests++;
  512.  
  513.   /* "Discard" boxes outside the shaft */
  514.   if (candidate == OUTSIDE) {
  515.     Update_ShaftStats(candidate, Candidate_type(hbox));
  516.     return 0;
  517.   }
  518.   /* else if at leaf level add to list */
  519.   else if (IsLeafBox(hbox)) {
  520.     Update_ShaftStats(candidate, Candidate_type(hbox));
  521.     AddTo_ObjectList(hbox,candidate);
  522.     return 1;
  523.   }
  524.   
  525.   /* Test if is a primitive of type cone, box, sphere etc. If so, then
  526.      if its inside or overlapping, just add to list. 
  527.      If contains only boxes can be discarded. */
  528.   if (hbox->object != 0) {
  529.     if (Candidate_type(hbox) != MESH) { /* Is not a mesh */
  530.       if ((candidate == INSIDE) || (candidate == OVERLAP)) {
  531.     Update_ShaftStats(candidate, Candidate_type(hbox));
  532.     AddTo_ObjectList(hbox,candidate);
  533.     atlevel_added++;
  534.       }
  535.       
  536.       /* If "contains" and is a box, nothing inside can intersect with 
  537.      shaft, else add to list (assume non-mesh ray-intersect test
  538.      less than ray-polygon intersect test */
  539.       else if (candidate == CONTAINS) { 
  540.     if (Candidate_type(hbox) != CUBE) {
  541.       Update_ShaftStats(candidate, Candidate_type(hbox));
  542.       AddTo_ObjectList(hbox,candidate);
  543.       atlevel_added++;
  544.     }
  545.       }
  546.       return atlevel_added;
  547.     } /* not mesh */
  548.   }
  549.  
  550.   /* If test box contains the extent box test descendents */
  551.   if (candidate == CONTAINS) {
  552.     children_added = 0;
  553.     same_father = FALSE;
  554.     for(i=0; i<hbox->num_children; i++) {
  555.       if (same_father == FALSE) 
  556.     same_father = Bounds_Same(hbox->box, hbox->child[i]->box);
  557.       children_added +=
  558.     Form_Candidate_List(shootPatch, recPatch, sbox, rbox, hbox->child[i]);
  559.     }
  560.  
  561.     /* Add containing box only if no descendents added, and box not same 
  562.        as any children, if any */
  563.     /* if (hbox->father != NULL)  */
  564.     if ((children_added == 0) && (!same_father)) {
  565.       if (fdbg) printf("Add contains\n");
  566.       Update_ShaftStats(candidate, Candidate_type(hbox));
  567.       AddTo_ObjectList(hbox,candidate);
  568.       atlevel_added++;
  569.     }
  570.     return children_added+atlevel_added;
  571.   }
  572.  
  573.   /* Test which strategy to use for list addition, if candidate
  574.      overlaps or is inside the shaft */
  575.   switch (ShaftStats.strategy) {
  576.   case KEEP_CLOSED: /* Never check children, even if overlaps */
  577.     if (fdbg) printf("Add keep closed\n");
  578.     Update_ShaftStats(candidate, Candidate_type(hbox));
  579.     AddTo_ObjectList(hbox,candidate);
  580.     atlevel_added++;
  581.     break;
  582.     
  583.   case ALWAYS_OPEN: /* Check all children bounding volumes */
  584.     children_added = 0;
  585.     for(i=0; i<hbox->num_children; i++) 
  586.       children_added +=
  587.     Form_Candidate_List(shootPatch, recPatch, sbox, rbox, hbox->child[i]);
  588.     
  589.     /* if (children_added == 0) {
  590.        if (fdbg) printf("Add always open\n");
  591.        Update_ShaftStats(candidate, Candidate_type(hbox));
  592.        AddTo_ObjectList(hbox,candidate);      
  593.        atlevel_added++;
  594.        } else */
  595.     atlevel_added += children_added;
  596.     break;
  597.  
  598.   case OVERLAP_OPEN: /* Check children bounding volumes only if overlaps */
  599.     if (candidate == OVERLAP || candidate == CONTAINS) {
  600.       children_added = 0;
  601.       for(i=0; i<hbox->num_children; i++) 
  602.     children_added += Form_Candidate_List(shootPatch, recPatch, 
  603.                           sbox, rbox, hbox->child[i]);
  604.       if (children_added == 0) {
  605.     if (fdbg) printf("Add overlap open\n");
  606.     Update_ShaftStats(candidate, Candidate_type(hbox));
  607.     AddTo_ObjectList(hbox,candidate);
  608.     atlevel_added++;
  609.       } else
  610.     atlevel_added += children_added;
  611.     } else if (candidate == INSIDE) {
  612.       if (fdbg) printf("Add overlap open\n");
  613.       Update_ShaftStats(candidate, Candidate_type(hbox));
  614.       AddTo_ObjectList(hbox,candidate);
  615.       atlevel_added++;
  616.     }
  617.     break;
  618.     
  619.   case RATIO_OPEN: /* Check children bounding volumes only if overlaps,
  620.               by given ratio */
  621.     if (candidate == OVERLAP || candidate == CONTAINS) {
  622.       percent_overlap = 0.0;
  623.       if (hbox->num_children != 0) {
  624.  
  625.     /* Find number of children that are inside or overlap the shaft */
  626.     for(i=0; i<hbox->num_children; i++) {
  627.       test_box = hbox->child[i]->box;
  628.       if (Bounds_Same(test_box, hbox->box)) {
  629.         overlap_id = i;
  630.         percent_overlap++;
  631.       } else if (isCandidate(test_box, &extentbox, sbox, rbox, planeset)
  632.              != OUTSIDE) {
  633.         overlap_id = i;
  634.         percent_overlap++;
  635.       }
  636.     }
  637.     
  638.     /* If only 1 child overlaps, just add it to candidate list */
  639.     /* Otherwise find percentage of children that overlap */
  640.     if (percent_overlap == 1) {
  641.       if (fdbg) printf("Add ratio open\n");
  642.       Update_ShaftStats(candidate, Candidate_type(hbox));
  643.       AddTo_ObjectList(hbox->child[overlap_id],candidate);      
  644.       atlevel_added++;
  645.       return atlevel_added;
  646.     } else
  647.       percent_overlap /= (float) hbox->num_children;
  648.       }
  649.  
  650.       /* Check if ratio of overlap > user defined tolerance */
  651.       if (percent_overlap > ShaftStats.ratio_open) {
  652.     if (fdbg) printf("Add ratio open. Percent = %g\n", percent_overlap);
  653.     Update_ShaftStats(candidate, Candidate_type(hbox));
  654.     AddTo_ObjectList(hbox,candidate);
  655.     atlevel_added++;
  656.       } else { /* Open box */
  657.     children_added = 0;
  658.     for(i=0; i<hbox->num_children; i++) 
  659.       children_added +=
  660.         Form_Candidate_List(shootPatch, recPatch, sbox, rbox, 
  661.                 hbox->child[i]);
  662.     if (children_added == 0) {
  663.       if (fdbg) printf("Add ratio open\n");
  664.       Update_ShaftStats(candidate, Candidate_type(hbox));
  665.       AddTo_ObjectList(hbox,candidate);
  666.       atlevel_added++;
  667.     } else
  668.       atlevel_added += children_added;
  669.       }
  670.  
  671.     } else if (candidate == INSIDE) {
  672.       if (fdbg) printf("Add ratio open\n");
  673.       Update_ShaftStats(candidate, Candidate_type(hbox));
  674.       AddTo_ObjectList(hbox,candidate);
  675.       atlevel_added++;
  676.     }
  677.     break;
  678.  
  679.   default:
  680.     fprintf(stderr,"Invalid cull strategy creating Clist\n");
  681.     exit(1);
  682.   }
  683.  
  684.   return atlevel_added;
  685. }
  686.  
  687. /**********************************************************************/
  688. /* Perform shaft culling between two patches                          */
  689. /**********************************************************************/
  690. void ShaftCull(src,rec, sbox, rbox, hbox)
  691.      Polygon *src, *rec;
  692.      BoundingBoxType sbox, rbox;
  693.      HBBox *hbox;
  694. {
  695.   Form_Culling_Shaft(sbox, rbox);
  696.   (void) Form_Candidate_List(src, rec, &sbox, &rbox, hbox);
  697. }
  698.